home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / quartz / quartz10.lha / src / runtime / profile.c < prev    next >
C/C++ Source or Header  |  1990-05-18  |  12KB  |  558 lines
  1. #include <stdio.h>
  2. #include "thread.h"
  3. #include "synch.h"
  4. #include <usclkc.h>
  5. #include "quartzcommon.h"
  6. #include "profile.h"
  7. #include "internal.h"
  8.  
  9. #ifndef InitOverflowSize
  10. #define InitOverflowSize     5000
  11. #endif
  12.  
  13. #define InitNumObjs            10
  14. #define InitNumKids            10
  15.  
  16. /* These get set by munge */
  17.  
  18. private int mNumProcIds = 0;
  19. private int mEndOfText = 0;
  20.  
  21.  
  22. /* communication from the computation -> sampling processors */
  23.  
  24. private int profileOn = FALSE;
  25.  
  26. shared int effectiveParallelism = 0;
  27. shared int nominalParallelism = 0;
  28. shared int profileOver = FALSE;
  29. shared Processor processorList[NUMPROCS];
  30.  
  31.  
  32. /* Sampled data -- output to a file */
  33.  
  34. shared FLOAT timeDiff = 0;
  35. shared int numSamples = 0;
  36.  
  37. shared ConcurrentData *procData;
  38.  
  39. shared GraphEntry *pcTable;        /* needed by mcount */
  40. shared int pcTableSize;
  41.  
  42.  
  43. /* Needed internally to control profiling */
  44.  
  45. static shared SpinLock    *pcTableLocks;
  46.  
  47. static shared GraphEntry overflowFirst[InitOverflowSize];
  48. static shared GraphEntry *overflow;
  49. static shared SpinLock overflowLock;
  50. static shared int overflowSize = 0;
  51. static shared int overflowOccurred = 0;
  52.  
  53. static shared SynchSamples *objData;
  54. static shared int objNum = 0;
  55. static shared SpinLock objLock;
  56.  
  57. static shared ChildData *kidData;
  58. static shared int kidNum = 0;
  59. static shared SpinLock kidLock;
  60.  
  61. private int iteration = 1;
  62. private unsigned int tmpStack[InitIdStackSize];
  63. private int myHit;
  64.  
  65. static shared int start = FALSE;
  66. static shared usclk_t startTime;
  67. static shared endCount;
  68. static shared SpinLock startLock;
  69.  
  70. void OutOfRoom();
  71.  
  72. /* Initialization routines */
  73.  
  74. /* Init profiling data structures */
  75. static void OverflowSetup (o)
  76.     GraphEntry *o;
  77.     {
  78.     GraphTableInit(o, InitOverflowSize);
  79.     overflow = o;
  80.     overflowSize = InitOverflowSize;
  81.     overflowOccurred = 0;
  82.     }
  83.  
  84. void ProcessorListInit ()
  85.     {
  86.     int i;
  87.     Thread *t;
  88.     Processor *p;
  89.  
  90.     for (i = 0; i < NUMPROCS; i++)
  91.         {
  92.         p = &processorList[i];
  93.  
  94.         t = &p->idleThread;
  95.         t->type = ThreadType;
  96.         t->idStack.base = &p->idStack[0];
  97.         if (i == 0)
  98.             t->idStack.base->procID = StartID | BusyState;
  99.         else
  100.             t->idStack.base->procID = StartID | SpinState;
  101.         t->idStack.top = t->idStack.base;
  102.         t->idStack.limit = t->idStack.base + InitIdStackSize - 1;
  103.  
  104.         p->curThread = t; 
  105.         p->synchList = NULL;
  106.         SLNPInit(&p->profLock);
  107.         p->numSamples = 0;
  108.         }
  109.     }
  110.  
  111. /* External entry point to initialize external data structures */
  112. void ProfileInit (numProfilers)
  113.     int numProfilers;
  114.     {
  115.     int i;
  116.  
  117.     if (mEndOfText == 0)
  118.         {
  119.         fprintf(stderr, "Unable to profile: munge not run on object\n");
  120.         exit(0);
  121.         }
  122.  
  123.     pcTableSize = (mEndOfText + sizeof(GraphEntry)) / sizeof(GraphEntry);
  124.     pcTable = MyShmalloc(GraphEntry, pcTableSize);
  125.     GraphTableInit(pcTable, pcTableSize);
  126.     pcTableLocks = MyShmalloc(SpinLock, pcTableSize);
  127.     for (i = 0; i < pcTableSize; i++)
  128.         SLNPInit(&pcTableLocks[i]);
  129.  
  130.     OverflowSetup(overflowFirst);
  131.     SLNPInit(&overflowLock);
  132.  
  133.     procData = MyShmalloc(ConcurrentData, mNumProcIds);
  134.     ConDataTableInit(procData, mNumProcIds);
  135.  
  136.     SLNPInit(&objLock);
  137.     SLNPInit(&kidLock);
  138.  
  139.     endCount = numProfilers;
  140.     SLNPInit(&startLock);
  141.     effectiveParallelism = nominalParallelism = 1;
  142.     }
  143.  
  144. void ProfileSetAllBusy ()
  145.     {
  146.     int i;
  147.  
  148.     for (i = 0; i < numProcessors; i++)
  149.         {
  150.         processorList[i].idleThread.idStack.top++;
  151.         processorList[i].idleThread.idStack.top->procID = ForkID | BusyState;
  152.         }
  153.     effectiveParallelism = nominalParallelism = numProcessors;
  154.     }
  155.  
  156. void SetProfileOn ()
  157.     {
  158.     profileOn = TRUE;
  159.     }
  160. void SetProfileOff ()
  161.     {
  162.     profileOn = FALSE;
  163.     }
  164.  
  165. /* Runtime profiling routines, for normal processors (eg, mcount) */
  166.  
  167. /* does the same thing as mcount, but ignore recursion */
  168. void TPushOnIdStack (t, p, s)    
  169.     register Thread *t;
  170.     register SynchProfile *p;
  171.     unsigned int s;
  172.     {
  173.       register IdStackEntry *ePtr;
  174.     unsigned int callerID;
  175.  
  176.     ASSERT(t->type == ThreadType);
  177.     ASSERT(p->type == SynchProfileType);
  178.       ePtr = t->idStack.top;
  179.       ePtr->procID |= OverheadState;
  180.     callerID = ePtr->procID & AllOffMask;
  181.     if (p->g.callerID == callerID)
  182.         AtomicIncrP(&(p->g.num));
  183.     else
  184.         ProfileMustAdd((unsigned int)p, callerID, &p->g);
  185.  
  186.       if (ePtr >= t->idStack.limit) 
  187.         OutOfRoom();    /* die */
  188.  
  189.       (ePtr + 1)->procID = NoID;
  190.       ePtr->procID &= OverheadOffMask;
  191.       t->idStack.top = ++ePtr;
  192.       ePtr->procID = (s) | (int)p;
  193.       }
  194.  
  195. void CallAndReplaceOnIdStack (p, s)
  196.     register SynchProfile *p;
  197.     unsigned int s;
  198.     {
  199.       register Thread *t = pP.thread;
  200.       register IdStackEntry *ePtr = t->idStack.top;
  201.     unsigned int callerID;
  202.  
  203.     ASSERT(p->type == SynchProfileType);
  204.       ePtr->procID |= OverheadState;
  205.     callerID = ePtr->procID & AllOffMask;
  206.     if (p->g.callerID == callerID)
  207.         AtomicIncrP(&(p->g.num));
  208.     else
  209.         ProfileMustAdd((unsigned int)p, callerID, &p->g);
  210.     ReplaceOnIdStack(p,s);
  211.     }
  212.  
  213.  
  214. /* nasty: how to make sure we're free from deadlock
  215.  * on overflow, provided the procedures we call don't overflow
  216.  * on interrupts 
  217.  */
  218.  
  219. void ProfileMustAdd (calleeID, callerID, p)
  220.     unsigned int calleeID;
  221.     unsigned int callerID;
  222.     GraphEntry *p;
  223.     {
  224.     register GraphEntry *q;
  225.     register SpinLock *l = NULL;    
  226.     register int old;
  227.  
  228.     for (q = p; q->calleeID != calleeID || q->callerID != callerID; q = q->next)
  229.         {
  230.         while (q->next == NULL)
  231.             {
  232.             if (!l)
  233.                 l = id2lock(calleeID);
  234.             old = profileOn;
  235.             profileOn = FALSE;        /* in case we get an interrupt */
  236.             if (!SLNPTestAndGet(l))
  237.                 {
  238.                 profileOn = old;
  239.                 continue;
  240.                 }
  241.             if (q->next != NULL)
  242.                 {
  243.                 SLNPRelease(l);
  244.                 profileOn = old;
  245.                 break;
  246.                 }
  247.             if (q->num != 0)    /* have to get one from overflow */
  248.                 {
  249.                 SLNPAcquire(&overflowLock);
  250.                 if (overflowSize == 0)
  251.                    OverflowSetup(MyShmalloc(GraphEntry,InitOverflowSize));
  252.                 q->next = &overflow[--overflowSize];
  253.                 SLNPRelease(&overflowLock);
  254.                 q = q->next;
  255.                 }
  256.             q->num = 1;
  257.             q->calleeID = calleeID;
  258.             q->callerID = callerID;
  259.             SLNPRelease(l);
  260.             profileOn = old;
  261.             return;
  262.             }
  263.         }
  264.     AtomicIncrP(&(q->num));
  265.     }
  266.  
  267. /* Runtime sampling routines */
  268.  
  269. /* return t1 - t2 */
  270. static FLOAT ComputeDiff (t1, t2)
  271.     usclk_t t1, t2;
  272.     {
  273.     usclk_t d;
  274.  
  275.     if (t1 < t2)
  276.         d = t1 + (0xffffffff - t2);
  277.     else
  278.         d = t1 - t2;
  279.     return((FLOAT)d);
  280.     }
  281.  
  282. static int Bound (n, lb, ub)
  283.     int n, lb, ub;
  284.     {
  285.     if (n < lb)
  286.         return(lb);
  287.     if (n > ub)
  288.         return(ub);
  289.     return(n);
  290.     }
  291.  
  292. static int SampleStack (t, eff, nom)
  293.     register Thread *t;
  294.     int *eff, *nom;
  295.     {
  296.     int eP, nP;
  297.     register IdStackEntry *e;
  298.     register unsigned int *sp = tmpStack;
  299.  
  300. /* Sampling begins */
  301.     eP = effectiveParallelism;
  302.     nP = nominalParallelism;
  303.  
  304.     for (e = t->idStack.top; e >= t->idStack.base; e--, sp++)
  305.         *sp = e->procID;
  306. /* Sampling ends */
  307.  
  308.     *eff = Bound(eP, 1, MaxEffectiveParallelism) - 1;
  309.     *nom = (nP < numProcessors) ? 0 : 1;
  310.     iteration++;
  311.     return(sp - tmpStack);
  312.     }
  313.  
  314. ChildData *GetChildData ()
  315.     {
  316.     ChildData *k;
  317.  
  318.     SLNPAcquire(&kidLock);
  319.     if (--kidNum < 0)
  320.         {
  321.         kidData = MyShmalloc(ChildData, InitNumKids);
  322.         ChildTableInit(kidData, InitNumKids);
  323.         kidNum = InitNumKids - 1;
  324.         }
  325.     k = &kidData[kidNum];
  326.     SLNPRelease(&kidLock);
  327.     return(k);
  328.     }
  329.  
  330. SynchSamples *GetSampleSpace ()
  331.     {
  332.     SynchSamples *s;
  333.  
  334.     SLNPAcquire(&objLock);
  335.     if (--objNum < 0)
  336.         {
  337.         objData = MyShmalloc(SynchSamples, InitNumObjs);
  338.         SynchTableInit(objData, InitNumObjs);
  339.         objNum = InitNumObjs - 1;
  340.         }
  341.     s = &objData[objNum];
  342.     SLNPRelease(&objLock);
  343.     return(s);
  344.     }
  345.  
  346. static void AddSample (data, diff, eP, nP, first, callee)
  347.     ConcurrentData *data;
  348.     FLOAT diff;
  349.     int eP, nP, first;
  350.     unsigned int callee;
  351.     {
  352.     ChildData *k;
  353.  
  354.     ASSERT(data->type == ConcurrentDataType && diff >= 0);
  355.     ASSERT((eP >= 0 && eP < MaxEffectiveParallelism) && (nP == 0 || nP == 1));
  356.     if (data->hit[myHit] < iteration)
  357.         {
  358.         data->hit[myHit] = iteration;
  359.         SLNPAcquire(&data->lock);
  360.         data->nom.byNomP[MePlusKids][BUSY][nP] += diff;
  361.         if (first)
  362.             {
  363.             data->busy.byEffP[eP] += diff;
  364.             data->nom.byNomP[JustMe][BUSY][nP] += diff;
  365.             }
  366.         else    /* mark where busy time came from */
  367.             {
  368.             for (k = &data->kid; k->calleeID != callee; k = k->next) 
  369.                 if (k->next == NULL)
  370.                     {
  371.                     if (k->calleeID != NoID)
  372.                         {
  373.                         k->next = GetChildData();
  374.                         k = k->next;
  375.                         }
  376.                     k->calleeID = callee;
  377.                     break;
  378.                     }
  379.             k->busy.byEffP[eP] += diff;
  380.             }
  381.         SLNPRelease(&data->lock);
  382.         }
  383.     }
  384.  
  385. static void AddNomSample (data, diff, nP, state, first)
  386.     ConcurrentData *data;
  387.     FLOAT diff;
  388.     int nP, state, first;
  389.     {
  390.     ASSERT(data->type == ConcurrentDataType && (nP == 0 || nP == 1));
  391.     ASSERT((state >= 0 || state < NumStates) && diff >= 0);
  392.     if (data->hit[myHit] < iteration)
  393.         {
  394.         data->hit[myHit] = iteration;
  395.         SLNPAcquire(&data->lock);
  396.         if (first)
  397.             data->nom.byNomP[JustMe][state][nP] += diff;
  398.         data->nom.byNomP[MePlusKids][state][nP] += diff;
  399.         SLNPRelease(&data->lock);
  400.         }
  401.     }
  402.  
  403. static ConcurrentData *id2data (id)
  404.     unsigned int id;
  405.     {
  406.     SynchProfile *p;
  407.  
  408.     id &= AllOffMask;
  409.     if (isSynchID(id))
  410.         {
  411.         p = (SynchProfile *)id;
  412.         ASSERT(p->type == SynchProfileType);
  413.         if (p->samples == NULL)
  414.             p->samples = GetSampleSpace();
  415.         return(&p->samples->data); 
  416.         }
  417.     return(&procData[id]);
  418.     }
  419.  
  420. static usclk_t ProfileProc (p)
  421.     Processor *p;
  422.     {
  423.     int i, stackDepth, eP, nP;
  424.     usclk_t next;
  425.     FLOAT diff;
  426.  
  427.     next = GETUSCLK();
  428.     stackDepth = SampleStack(p->curThread, &eP, &nP);
  429.     diff = ComputeDiff(next, p->lastSample);
  430.     p->lastSample = next;
  431.  
  432.     if (stackDepth == 0 || isOverhead(tmpStack[0]))
  433.         AddSample(&procData[NoID], diff, eP, nP, TRUE, NoID);
  434.     else if (isSpinning(tmpStack[0]))
  435.         for (i = 0; i < stackDepth; i++)
  436.             AddNomSample(id2data(tmpStack[i]), diff, nP, SPIN, i == 0);
  437.     else
  438.         {
  439.         AddSample(id2data(tmpStack[0]), diff, eP, nP, TRUE, NoID);
  440.         for (i = stackDepth - 1; i > 0; i--)
  441.             AddSample(id2data(tmpStack[i]), diff, eP, nP, FALSE, 
  442.                 (unsigned int)(tmpStack[i-1] & AllOffMask));
  443.         }
  444.     }
  445.  
  446. static void ProfileSynch (p)
  447.     SynchProfile *p;
  448.     {
  449.     int i, n[NumNumbers];
  450.     usclk_t next;
  451.     FLOAT diff;
  452.     register Thread *t;
  453.     int stackDepth, eP, nP, type;
  454.  
  455.     if (p->status != ACTIVE)
  456.         return;
  457.     for (i = 0; i < NumNumbers; i++)
  458.         n[i] = p->number[i];
  459.     next = GETUSCLK();
  460.     if (t = p->thread)
  461.         stackDepth = SampleStack(t, &eP, &nP);
  462.     diff = ComputeDiff(next, p->lastSample);
  463.     if (t && stackDepth != 0 && !isOverhead(tmpStack[0]) && !isBusy(tmpStack[0])
  464.                     && !isSpinning(tmpStack[0]))
  465.         {
  466.         if (isBlocked(tmpStack[0]))
  467.             type = BLOCKED;
  468.         else 
  469.             type = READY;
  470.         for (i = 0; i < stackDepth; i++)
  471.             AddNomSample(id2data(tmpStack[i]), diff, nP, type, i == 0);
  472.         }
  473.     if (!p->samples)
  474.         p->samples = GetSampleSpace();
  475.     for (i = 0; i < NumNumbers; i++)
  476.         {
  477.         n[i] = Bound(n[i], 0, MaxNominalParallelism - 1);
  478.         p->samples->queue.length[i][n[i]] += diff;
  479.         }
  480.     p->lastSample = next;
  481.     }
  482.  
  483. void ProfileExternal ()
  484.     {
  485.     register int i;
  486.     register Processor *p;
  487.     register SynchProfile *s;
  488.  
  489.     SLNPAcquire(&startLock);
  490.     if (!start)
  491.         {
  492.         start = TRUE;
  493.         startTime = GETUSCLK();
  494.         for (i = 0; i < numProcessors; i++)
  495.             processorList[i].lastSample = startTime;
  496.         }
  497.     SLNPRelease(&startLock);
  498.     myHit = pP.myId - numProcessors;
  499.  
  500.     while (!profileOver)
  501.         {
  502.         for (i = 0; i < numProcessors && !profileOver; i++)
  503.             {
  504.             p = &processorList[i];
  505.             if (SLNPTestAndGet(&p->profLock))
  506.                 {
  507.                 ProfileProc(p);
  508.                 for (s = p->synchList; s && !profileOver; s = s->next)
  509.                     ProfileSynch(s);
  510.                 p->numSamples++;
  511.                 SLNPRelease(&p->profLock);
  512.                 }
  513.             }
  514.         }
  515.     SLNPAcquire(&startLock);
  516.     if (--endCount == 0)    /* wait for everybody to check in */
  517.         {
  518. #ifndef DEBUG
  519.         KillAll();
  520. #endif
  521.         for (i = 0; i < numProcessors; i++)
  522.             {
  523.             timeDiff += ComputeDiff(processorList[i].lastSample, startTime);
  524.             numSamples += processorList[i].numSamples;
  525.             }
  526.         timeDiff /= numProcessors;
  527.         numSamples /= numProcessors;
  528.         DumpInfo();
  529. #ifdef DEBUG
  530.         KillAll();
  531. #endif
  532.         }
  533.     SLNPRelease(&startLock);
  534.     exit(0);
  535.     }
  536.  
  537. void TooHigh ()
  538.     {
  539.     printf("Fatal error: mcount() passed an out-of-bound processor ID.\n");
  540.     fflush(stdout);
  541.     KillAll();
  542.     exit(1);
  543.     }
  544.  
  545. void OutOfRoom ()
  546.     {
  547.     printf("Fatal error: profiler ID stack is out of room.\n");
  548.     fflush(stdout);
  549.     KillAll();
  550.     exit(1);
  551.     }
  552.  
  553. void ProfileFinish ()
  554.     {
  555.     profileOver = TRUE;
  556.     }
  557.  
  558.